package com.ashbur.insertionsort;

/**
 * @author : Eumenides
 * @Description :
 * @date : 2022/7/21
 * @Copyright ： 公众号：菜鸟的大厂梦
 */
public class InsertionSort {

    private InsertionSort() {}

    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 将arr[i]插入到合适的位置
//            for (int j = i; j - 1 > 0 ; j--) {
//                if (arr[j].compareTo(arr[j - 1]) < 0) {
//                    swap(arr, j, j-1);
//                } else {
//                    break;
//                }
//            }
            for (int j = i; j - 1 >= 0 && arr[j].compareTo(arr[j - 1]) < 0 ; j--) {
                swap(arr, j, j-1);
            }

        }
    }

    public static <E extends Comparable<E>> void sort2(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            E t = arr[i];
            int j;
            for (j = i ; j-1 >= 0 && t.compareTo(arr[j-1]) < 0; j--) {
                arr[j] = arr[j-1];
            }
            arr[j] = t;
        }
    }

    private static <E> void swap(E[] arr, int j, int i) {

        E t = arr[i];

        arr[i] = arr[j];

        arr[j] = t;


    }


}
